// Learning the OpenMP framework with GCC
// Arpan Sen (arpansen@gmail.com)
//
// http://www.ibm.com/developerworks/aix/library/au-aix-openmp-framework/?S_TACT=105AGX99&S_CMP=CP
// При використанні 8 потоків для виконання процедури merge sort час виконання скоротилося з 3,7 
// (при використанні одного потоку) до 2,1 секунди. 
// Необхідно лише бути обачним з кількістю потоків. У прикладі програми є 8 потоків, 
// але реальна віддача від їх використання може змінюватись в залежності від конфігурації системи. 
// Якщо кількість потоків не обмежена явним чином, то можуть бути створені сотні, якщо не тисячі потоків, 
// що з дуже високою ймовірністю призведе до зниження продуктивності системи. 
// Крім того, при роботі з кодом merge sort корисно використовувати прагму sections, яка була розглянута у відповідному розділі.
//
#include <omp.h>
#include <vector>
#include <iostream>
using namespace std;

vector<long> merge(const vector<long>& left, const vector<long>& right)
{
    vector<long> result;
    unsigned left_it = 0, right_it = 0;

    while(left_it < left.size() && right_it < right.size())
    {
        if(left[left_it] < right[right_it])
        {
            result.push_back(left[left_it]);
            left_it++;
        }
        else					
        {
            result.push_back(right[right_it]);
            right_it++;
        }
    }

    // Занесение оставшихся данных из обоих векторов в результирующий
    while(left_it < left.size())
    {
        result.push_back(left[left_it]);
        left_it++;
    }

    while(right_it < right.size())
    {
        result.push_back(right[right_it]);
        right_it++;
    }

    return result;
}

vector<long> mergesort(vector<long>& vec, int threads)
{
    // Условие завершения: список полностью отсортирован,
    // если он содержит только один элемент.
    if(vec.size() == 1)
    {
        return vec;
    }

    // Определяем местоположение среднего элемента в векторе
    std::vector<long>::iterator middle = vec.begin() + (vec.size() / 2);

    vector<long> left(vec.begin(), middle);
    vector<long> right(middle, vec.end());

    // Выполнение сортировки слиянием над двумя меньшими векторами

    if (threads > 1)
    {
      #pragma omp parallel sections
      {
        #pragma omp section
        {
          left = mergesort(left, threads/2);
        }
        #pragma omp section
        {
          right = mergesort(right, threads - threads/2);
        }
      }
    }
    else
    {
      left = mergesort(left, 1);
      right = mergesort(right, 1);
    }

    return merge(left, right);
}

int main()
{
  vector<long> v(1000000);
  for (long i=0; i<1000000; ++i)
    v[i] = (i * i) % 1000000;
  v = mergesort(v, 1);
  for (long i=0; i<1000000; ++i)
    cout << v[i] << "\n";
}
